package com.example.leetcode.linklist;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 环形链表 II
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 */
public class HasCycle2 {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(3);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(0);
        ListNode listNode3 = new ListNode(-4);

        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode1;

        detectCycle2(listNode);
    }

    public static ListNode detectCycle2(ListNode head) {
        ListNode currrent = head;

        Set<Integer> set =new HashSet<>();

        while(currrent != null) {
            if (set.contains(currrent.val)) {
                return currrent;
            }
            set.add(currrent.val);
            currrent = currrent.next;
        }
        return null;
    }



}
